﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using GridRegulator;

namespace NoahSolver
{
    public static class Solver
    {
        public struct Solution
        {
            public int I0, J0;
            public int I1, J1;

            public bool Horizontal;
            public int Beam;

            public Solution(int i0, int j0, int i1, int j1, bool horizontal, int beam)
            {
                I0 = i0;
                J0 = j0;
                I1 = i1;
                J1 = j1;
                Horizontal = horizontal;
                Beam = beam;
            }
        }

        public class Solutions : List<Solution>
        {
        }

        const int kCheckingFailed = -2;

        static int CheckVerticalRight(IPetGrid grid, int jleft, int jright, int ilow, int ihigh)
        {
            for (int j = jleft; j <= jright; j++)
            {
                int i;
                for (i = ilow + 1; i < ihigh && grid[i, j] < 0; i++)
                {
                }
                if (i == ihigh)
                {
                    return i;
                }
            }
            if (jleft <= 0) return -1;
            if (jright >= grid.N - 1) return grid.M;
            return kCheckingFailed;
        }

        static int CheckVerticalLeft(IPetGrid grid, int jright, int jleft, int ilow, int ihigh)
        {
            for (int j = jright; j >= jleft; j--)
            {
                int i;
                for (i = ilow + 1; i < ihigh && grid[i, j] < 0; i++)
                {
                }
                if (i == ihigh)
                {
                    return i;
                }
            }
            if (jleft <= 0) return -1;
            return kCheckingFailed;
        }

        static int CheckHorizontalDown(IPetGrid grid, int iup, int idown, int jlow, int jhigh)
        {
            for (int i = iup; i <= idown; i++)
            {
                int j;
                for (j = jlow + 1; j < jhigh && grid[i, j] < 0; j++)
                {
                }
                if (j == jhigh)
                {
                    return i;
                }
            }
            if (iup <= 0) return -1;
            if (idown >= grid.M - 1) return grid.M;
            return kCheckingFailed;
        }

        static int CheckHorizontalUp(IPetGrid grid, int idown, int iup, int jlow, int jhigh)
        {
            for (int i = idown; i >= iup; i--)
            {
                if (i == -1) return i;
                int j;
                for (j = jlow + 1; j < jhigh && grid[i, j] < 0; j++)
                {
                }
                if (j == jhigh)
                {
                    return i;
                }
            }
            if (iup <= 0) return -1;
            return kCheckingFailed;
        }

        static int SolveVertical(IPetGrid grid, int i0, int j0, int i1, int j1)
        {
            if (i0 == i1) return kCheckingFailed;

            int ilow = Math.Min(i0, i1);
            int ihigh = Math.Max(i0, i1);
            int jlow = Math.Min(j0, j1);
            int jhigh = Math.Max(j0, j1);

            int jr = kCheckingFailed;

            // search paths in between horizontally

            int j0left, j0right;
            for (j0right = j0 + 1; j0right < grid.N && grid[i0, j0right] < 0; j0right++)
            {
            }
            j0right--;
            for (j0left = j0 - 1; j0left >= 0 && grid[i0, j0left] < 0; j0left--)
            {
            }
            j0left++;

            int j1left, j1right;
            for (j1right = j1 + 1; j1right < grid.N && grid[i1, j1right] < 0; j1right++)
            {
            }
            j1right--;
            for (j1left = j1 - 1; j1left >= 0 && grid[i1, j1left] < 0; j1left--)
            {
            }
            j1left++;

            int jleft = Math.Max(j0left, j1left);
            int jright = Math.Min(j0right, j1right);

            if (jleft <= jright)
            {
                if (jleft >= jlow)
                {
                    jr = CheckVerticalRight(grid, jleft, jright, ilow, ihigh);
                }
                else if (jright > jhigh)
                {
                    jr = CheckVerticalRight(grid, jlow, jhigh, ilow, ihigh);
                    if (jr != kCheckingFailed) return jr;
                    jr = CheckVerticalLeft(grid, jlow - 1, jleft, ilow, ihigh);
                    if (jr != kCheckingFailed) return jr;
                    jr = CheckVerticalRight(grid, jhigh + 1, jright, ilow, ihigh);
                }
                else if (jright < jlow)
                {
                    jr = CheckVerticalLeft(grid, jright, jleft, ilow, ihigh);
                }
                else
                {
                    jr = CheckVerticalRight(grid, jlow, jright, ilow, ihigh);
                    if (jr != kCheckingFailed) return jr;
                    jr = CheckVerticalLeft(grid, jlow - 1, jleft, ilow, ihigh);
                }
            }

            return jr;
        }


        static int SolveHorizontal(IPetGrid grid, int i0, int j0, int i1, int j1)
        {
            if (j0 == j1) return kCheckingFailed;

            int ilow = Math.Min(i0, i1);
            int ihigh = Math.Max(i0, i1);
            int jlow = Math.Min(j0, j1);
            int jhigh = Math.Max(j0, j1);

            int ir = kCheckingFailed;

            // search paths in between horizontal

            int i0up, i0down;
            for (i0down = i0 + 1; i0down < grid.M && grid[i0down, j0] < 0; i0down++)
            {
            }
            i0down--;
            for (i0up = i0 - 1; i0up >= 0 && grid[i0up, j0] < 0; i0up--)
            {
            }
            i0up++;

            int i1up, i1down;
            for (i1down = i1 + 1; i1down < grid.M && grid[i1down, j1] < 0; i1down++)
            {
            }
            i1down--;
            for (i1up = i1 - 1; i1up >= 0 && grid[i1up, j1] < 0; i1up--)
            {
            }
            i1up++;

            int iup = Math.Max(i0up, i1up);
            int idown = Math.Min(i0down, i1down);

            if (iup <= idown)
            {
                if (iup >= ilow)
                {
                    ir = CheckHorizontalDown(grid, iup, idown, jlow, jhigh);
                }
                else if (idown > ihigh)
                {
                    ir = CheckHorizontalDown(grid, ilow, ihigh, jlow, jhigh);
                    if (ir != kCheckingFailed) return ir;
                    ir = CheckHorizontalUp(grid, ilow - 1, iup, jlow, jhigh);
                    if (ir != kCheckingFailed) return ir;
                    ir = CheckHorizontalDown(grid, ihigh + 1, idown, jlow, jhigh);
                }
                else if (idown < ilow)
                {
                    ir = CheckHorizontalUp(grid, idown, iup, jlow, jhigh);
                }
                else
                {
                    ir = CheckHorizontalDown(grid, ilow, idown, jlow, jhigh);
                    if (ir != kCheckingFailed) return ir;
                    ir = CheckHorizontalUp(grid, ilow - 1, iup, jlow, jhigh);
                }
            }

            return ir;
        }

        public static Solutions Solve(IPetGrid grid)
        {
            PetList pets = grid.Pets;
            Solutions solutions = new Solutions();
            foreach (Pet pet in pets)
            {
                for (int a = 0; a < pet.Count - 1; a++)
                {
                    Pos pa = pet[a];
                    for (int b = a + 1; b < pet.Count; b++)
                    {
                        Pos pb = pet[b];

                        int beam = SolveHorizontal(grid, pa.I, pa.J, pb.I, pb.J);
                        if (beam != kCheckingFailed)
                        {
                            Solution sol = new Solution(pa.I, pa.J, pb.I, pb.J, true, beam);
                            solutions.Add(sol);
                            continue;
                        }

                        beam = SolveVertical(grid, pa.I, pa.J, pb.I, pb.J);
                        if (beam != kCheckingFailed)
                        {
                            Solution sol = new Solution(pa.I, pa.J, pb.I, pb.J, false, beam);
                            solutions.Add(sol);
                        }
                    }
                }
            }

            return solutions;
        }
    }
}
